Multiplicative Group Of Integers Modulo $n$

Precisely which elements are in ${\mathbb{U}}_n$ can be categorised by the following theorem:

Proof

This fact follows very naturally from the Bezout identity, specifically, consider that the equation

has a solution in $x$ if and only if there exists an $x,y$ solving the equivalent equation:

which occurs if and only $\gcd (a,p)\mid 1$ which is equivalent to $\gcd (a,p)=1$.

This fact then gives the basis for determining when ${\mathbb{Z}}_n$ is a field, that is the finite field of integers modulo $p$.